# import numpy as np  
# import matplotlib.pyplot as plt  
# from matplotlib.animation import FuncAnimation  
# from matplotlib.animation import FFWriter  
  
# def initialize_grid(size):  
#     """随机初始化一个size*size的网格，每个位置都是0或1"""  
#     return np.random.choice([0, 1], size=(size, size))  
  
# def count_neighbors(grid, row, col):  
#     """计算给定位置(row, col)的周围邻居（包括对角线）的活细胞数量"""  
#     height, width = grid.shape  
#     neighbors = sum([  
#         grid[(row-1)%height, (col-1)%width], grid[(row-1)%height, col], grid[(row-1)%height, (col+1)%width],  
#         grid[row, (col-1)%width],                            grid[row, (col+1)%width],  
#         grid[(row+1)%height, (col-1)%width], grid[(row+1)%height, col], grid[(row+1)%height, (col+1)%width]  
#     ])  
#     return neighbors  
  
# def evolve(grid):  
#     """根据生命游戏的规则更新网格"""  
#     next_grid = grid.copy()  
#     height, width = grid.shape  
#     for i in range(height):  
#         for j in range(width):  
#             neighbors = count_neighbors(grid, i, j)  
#             if grid[i, j] == 1:  # 当前位置是活的  
#                 if neighbors < 2 or neighbors > 3:  # 少于2个或超过3个邻居则死亡  
#                     next_grid[i, j] = 0  
#             else:  # 当前位置是死的  
#                 if neighbors == 3:  # 恰好有3个邻居则出生  
#                     next_grid[i, j] = 1  
#     return next_grid  
  
# def visualize_game(grid, size, interval=100, frames=500, save_as=None):  
#     """使用matplotlib可视化生命游戏"""  
#     fig, ax = plt.subplots()  
#     im = ax.imshow(grid, cmap='gray_r', vmin=0, vmax=1)  
  
#     def update(frame_number):  
#         grid = evolve(grid)  
#         im.set_data(grid)  
#         return im,  
  
#     ani = FuncAnimation(fig, update, frames=frames, interval=interval, repeat=False)  
  
#     # 如果指定了save_as，则将动画保存为视频文件  
#     if save_as:  
#         # 这里假设你已经安装了ffmpeg或者相应的编解码器  
#         writer = FFMpegWriter(fps=1000/interval)  
#         ani.save(save_as, writer=writer)  
  
#     plt.show()  
  
# # 设置网格大小  
# size = 100  
# grid = initialize_grid(size)  
  
# # 可视化生命游戏，并保存为视频（如果需要）  
# visualize_game(grid, size, interval=100, frames=500, save_as='game_of_life.mp4')

""""
import random  
import string  
  
def generate_password(n):  
    # 确定密码长度  
    length = n 
      
    # 确定密码的字符集，包括大小写字母、数字和特殊字符  
    characters = string.ascii_letters + string.digits + string.punctuation  
      
    # 生成密码  
    password = ''.join(random.choice(characters) for i in range(length))  
      
    return password  
  
# 生成并打印密码  
password = generate_password(int(input()))  
print(password)
"""


"""
import time
import  numpy as np


def jackknife_mean(x):
    n = len(x)
    result = np.zeros(n)

    for i in range(n):
        y = np.delete(x,i)
        result[i] = np.mean(y)
    return np.var(result) / n


def jackknife_mean_new(x):
    n = len(x)
    result = np.zeros(n)

    y = x
    for i in range(n):
        y[i] = 0
        result[i] = np.sum(y) / (len(y) - 1)
        y[i] = x[i]
    return np.var(result) / n

n = int(1e4)
x = np.random.randint(100, 301, size=n)

start_time = time.time()
print(jackknife_mean(x))
end_time = time.time()
print(f"运行耗时: {end_time - start_time} 秒")

start_time = time.time()
print(jackknife_mean_new(x))
end_time = time.time()
print(f"运行耗时: {end_time - start_time} 秒")
"""

"""
import numpy as np


def lagrange_polynomial(x, xp, yp):
    n = len(xp)
    p = 0
    for j in range(n):
        pj = yp[j]
        for k in range(n):
            if k != j:
                pj *= (x - xp[k]) / (xp[j] - xp[k])
        p += pj
    return p


# 数据点
x_data = np.array([0, 1, 2, 3, 5])
y_data = np.array([0, 1, 2, 3, 15])

# 使用拉格朗日插值
x_interp = np.linspace(0, 5, 100)
y_interp = [lagrange_polynomial(xi, x_data, y_data) for xi in x_interp]

# 绘图
import matplotlib.pyplot as plt

plt.plot(x_data, y_data, 'o', label='Data Points')
plt.plot(x_interp, y_interp, '-', label='Lagrange Interpolation')
plt.legend()
plt.show()


from scipy.interpolate import interp1d

# 三次样条插值
cubic_interp = interp1d(x_data, y_data, kind='cubic')
y_interp_cubic = cubic_interp(x_interp)

# 绘图
plt.figure()
plt.plot(x_data, y_data, 'o', label='Data Points')
plt.plot(x_interp, y_interp_cubic, '-', label='Cubic Spline Interpolation')
plt.legend()
plt.show()
print( cubic_interp(4))
"""

"""
import random  
import string  
  
def generate_random_string(length=10, mode='lowercase'):  
    chars = string.ascii_lowercase if mode == 'lowercase' else string.ascii_letters  
    if mode not in {'lowercase', 'mixedcase'}:  
        raise ValueError("Invalid mode. Choose 'lowercase' or 'mixedcase'.")  
    return ''.join(random.choices(chars, k=length))  # 使用choices一次性生成列表  
  
def compress_string(s):  
    if not s:  
        return ''  
    compressed_parts = []  # 使用列表存储压缩后的部分  
    count = 1  
    current_char = s[0]  
    for char in s[1:]:  
        if char == current_char:  
            count += 1  
        else:  
            if count > 1:  
                compressed_parts.append(str(count) + current_char)  
            else:  
                compressed_parts.append(current_char)  
            current_char = char  
            count = 1  
    # 处理最后一个字符及其计数  
    if count > 1:  
        compressed_parts.append(str(count) + current_char)  
    else:  
        compressed_parts.append(current_char)  
    return ''.join(compressed_parts)  # 最后一次性连接  
  
# 测试和性能评估  
total_length = 0  
total_compressed_length = 0  
iterations = 100  # 增加迭代次数以获得更稳定的平均值  

xx = []
for i in range(100):
    x = 0
    for j in range(10000):
        str1 = generate_random_string(10*(i + 1))
        c_str1 = compress_string(str1)
        x = x + (len(c_str1) / len(str1))
    x /= 1000
    xx.append(x)
print(xx)

x0 = range(len(xx))  
  
# 绘制折线图  
plt.plot(x0, xx, marker='o')   
  
# 添加标题和标签  
plt.title('Line Plot of Vector xx')  
plt.xlabel('Index')  
plt.ylabel('Value')  
  
# 显示图形  
plt.show()
"""

"""
def p(s):
    # 初始化一个空的结果列表
    result = []
    # 遍历输入字符串的每个字符
    for i in s:
        # 如果结果列表非空且最后一个字符与当前字符相同，则移除最后一个字符
        if result and result[-1] == i:
            result.pop()
        else:
            # 否则，将当前字符添加到结果列表中
            result.append(i)
            # 将结果列表转换为字符串并返回
    return "".join(result)


# 测试字符串
l = "abbaca"
print(p(l))  # 应输出 "ca"
"""


# import numpy as np  
# import scipy.integrate as integrate  
# import matplotlib.pyplot as plt  
# import time  
  
# # 定义质量点类  
# class MassPoint:  
#     def __init__(self, m, x, y, z):  
#         self.m = m  
#         self.x = x  
#         self.y = y  
#         self.z = z  
  
# # 定义椭球类  
# class Ellipsoid:  
#     def __init__(self, m, a, b, c):  
#         self.m = m  
#         self.a = a  
#         self.b = b  
#         self.c = c  
  
#     def Ellipsoid_V(self, masspoint, integral_func, G=6.67430e-11):  
#         Mass = self.m  
#         mass = masspoint.m  
  
#         k = -(3 * G * Mass * mass) / (4 * np.pi)  
  
#         # 定义被积函数  
#         def integrand_V(varphi, theta, r):  
#             return integrand_V_inner(varphi, theta, r, self, masspoint)  
  
#         # 进行三重积分  
#         res, _ = integral_func(integrand_V, 0, np.pi, lambda theta: 0, lambda theta: 2*np.pi, lambda varphi, theta: 0, lambda varphi, theta: 1)  
#         return k * res  
  
# # 定义内部被积函数  
# def integrand_V_inner(varphi, theta, r, ellipsoid, masspoint):  
#     a = ellipsoid.a  
#     b = ellipsoid.b  
#     c = ellipsoid.c  
  
#     x = a * r * np.cos(theta) * np.sin(varphi)  
#     y = b * r * np.sin(theta) * np.sin(varphi)  
#     z = c * r * np.cos(varphi)  
  
#     x0 = masspoint.x  
#     y0 = masspoint.y  
#     z0 = masspoint.z  
  
#     dx = x - x0  
#     dy = y - y0  
#     dz = z - z0  
  
#     R = np.sqrt(dx**2 + dy**2 + dz**2)  
  
#     # 当 R 小于阈值时，返回 0  
#     if R < 1e-2:  
#         return 0  
#     else:  
#         return (r**2 * np.sin(varphi)) / R  
  
# # 定义三重积分的蒙特卡洛方法  
# def integral3_monte_carlo(fun, xmin, xmax, ymin, ymax, zmin, zmax, N=1e6):  
#     x = xmin + (xmax - xmin) * np.random.rand(N)  
#     y = ymin + (ymax - ymin) * np.random.rand(N)  
#     z = zmin + (zmax - zmin) * np.random.rand(N)  
  
#     F = fun(x, y, z)  
  
#     # 移除 NaN 和 Inf 值  
#     valid_indices = ~np.isnan(F) & ~np.isinf(F)  
#     F = F[valid_indices]  
  
#     V = (xmax - xmin) * (ymax - ymin) * (zmax - zmin)  
#     return V * np.mean(F), None  
  
# # 定义三重积分的网格法  
# def integral3_grid(fun, xmin, xmax, ymin, ymax, zmin, zmax, n=200):  
#     x = np.linspace(xmin, xmax, n)  
#     y = np.linspace(ymin, ymax, n)  
#     z = np.linspace(zmin, zmax, n)  
  
#     X, Y, Z = np.meshgrid(x, y, z, indexing='ij')  
#     F = fun(X, Y, Z)  
  
#     # 将 NaN 和 Inf 值设为 0  
#     F[np.isnan(F) | np.isinf(F)] = 0  
  
#     dx = (xmax - xmin) / (n - 1)  
#     dy = (ymax - ymin) / (n - 1)  
#     dz = (zmax - zmin) / (n - 1)  
#     dV = dx * dy * dz  
  
#     return np.sum(F) * dV, None  
  
# # 已知参数  
# G = 1  
# M = 1  
# m = 1  
  
# # 椭球参数  
# a = 1  
# b = 1  
# c = 1  
  
# # 球体半径  
# R = 1  
  
# # 定义 x 的范围和分割次数  
# n = 30 
# x = np.linspace(0, 3, n)  
  
# # 初始化椭球和引力势数组  
# ellipsoid = Ellipsoid(M, a, b, c)  
# V_ellipsoid1 = np.zeros(n)  
# V_ellipsoid2 = np.zeros(n)  
# V_ellipsoid3 = np.zeros(n)  
  
# # 计算每种方法的开始时间  
# start_time = time.time()  
  
# # 循环遍历 x 值，计算椭球的引力势，采用普通三重积分  
# for i in range(n):  
#     mass_point = MassPoint(m, 0, 0, x[i])  
#     V_ellipsoid1[i] = ellipsoid.Ellipsoid_V(mass_point, integrate.tplquad)  
  
# time1 = time.time() - start_time  
  
# start_time = time.time()  
  
# # 循环遍历 x 值，计算椭球的引力势，采用网格法  
# for i in range(n):  
#     mass_point = MassPoint(m, 0, 0, x[i])  
#     V_ellipsoid2[i], _ = ellipsoid.Ellipsoid_V(mass_point, integral3_grid)  
  
# time2 = time.time() - start_time  
  
# start_time = time.time()  
  
# # 循环遍历 x 值，计算椭球的引力势，采用蒙特卡洛法  
# for i in range(n):  
#     mass_point = MassPoint(m, 0, 0, x[i])  
#     V_ellipsoid3[i], _ = ellipsoid.Ellipsoid_V(mass_point, integral3_monte_carlo)  
  
# time3 = time.time() - start_time  
  
# # 初始化球体引力势数组  
# V_sphere = np.zeros(n)  
  
# # 计算理论值  
# for i in range(n):  
#     if x[i] <= R:  
#         V_sphere[i] = -(G * M * m / R) * (3/2 - (x[i]**2 / (2 * R**2)))  
#     else:  
#         V_sphere[i] = -(G * M * m / x[i])  
  
# # 计算误差  
# error1 = np.abs(V_ellipsoid1 - V_sphere)  
# error2 = np.abs(V_ellipsoid2 - V_sphere)  
# error3 = np.abs(V_ellipsoid3 - V_sphere)  
  
# # 绘制三种方法的误差图，画在一张图上  
# plt.plot(x, error1, 'r-', label='三重积分法误差')  
# plt.plot(x, error2, 'g-', label='网格法误差')  
# plt.plot(x, error3, 'b-', label='蒙特卡洛法误差')  
# plt.xlabel('x 值')  
# plt.ylabel('误差')  
# plt.legend()  
# plt.title('三种积分方法计算椭球引力势的误差比较')  
# plt.grid(True)  
# plt.show()  
  
# # 输出每种方法的运行时间  
# print(f'三重积分法运行时间: {time1:.4f} 秒')  
# print(f'网格法运行时间: {time2:.4f} 秒')  
# print(f'蒙特卡洛法运行时间: {time3:.4f} 秒')

# from collections import deque  
  
# def maxSlidingWindows(nums: list, k: int) -> list:  
#     n = len(nums)  
#     ans = [0] * (n - k + 1)  
#     decreasing_queue = deque()  
  
#     for i in range(n):   
#         while len(decreasing_queue) > 0 and nums[i] >= nums[decreasing_queue[-1]]:  
#             decreasing_queue.pop()  
          
#         decreasing_queue.append(i)  
          
#         if (i - k + 1 > decreasing_queue[0]):
#                 decreasing_queue.popleft()

#         if i >= k - 1:
#             ans[i - k + 1] = nums[decreasing_queue[0]]
      
#     return ans  
  

# nums = [1, 3, -1, -3, 5, 3, 6, 7]  
# k = 3 

# print(maxSlidingWindows(nums, k))




# class Node:  
#     def __init__(self, value):  
#         self.value = value  
#         self.next = None  
  
#     def push_back(self, value):  
#         new_node = Node(value)  
#         # 找到尾节点  
#         curr = self  
#         while curr.next != None:  
#             curr = curr.next  
#         # 尾插  
#         curr.next = new_node  
  
#     def pop_back(self):  
#         # 如果链表为空，则无法移除节点  
#         if self.next is None:  
#             raise IndexError("pop_back from empty list")  
          
#         # 如果链表只有一个节点，则移除该节点并返回其值  
#         if self.next.next is None:  
#             popped_value = self.next.value  
#             self.next = None  
#             return popped_value  
          
#         # 找到倒数第二个节点  
#         curr = self  
#         while curr.next.next != None:  
#             curr = curr.next  
#         # 移除最后一个节点  
#         popped_value = curr.next.value  
#         curr.next = None  
#         return popped_value  
      
#     # 打印链表  
#     def Print(self):  
#         curr = self  
#         while curr != None:  
#             print(f"{curr.value}->", end="")  
#             curr = curr.next  
#         print("None")  
  
# # 使用示例  
# head = Node(1)  
# head.push_back(2)  
# head.push_back(3)  
# head.Print()  # 输出: 1->2->3->None  
# print(head.pop_back())  # 输出: 3  
# head.Print()  # 输出: 1->2->None  
# print(head.pop_back())  # 输出: 2  
# head.Print()  # 输出: 1->None  
# try:  
#     print(head.pop_back())  # 将引发 IndexError  
# except IndexError as e:  
#     print(e)  # 输出: pop_back from empty list

# import time  
# import matplotlib.pyplot as plt  
  
# # 初始化一个列表来存储不同n值下的计算耗时  
# time_n = [0] * 100000  
  
# # 迭代从1到9999，计算每个n值下的等差数列求和耗时  
# for n in range(1, 100000):  
#     start_time = time.time()  # 获取开始时间  
#     s = 0  
#     for j in range(n):  
#         s = s + j  # 使用迭代法计算等差数列求和  
#     end_time = time.time()  # 获取结束时间  
#     time_n[n - 1] = end_time - start_time  # 计算耗时并存入time_n列表  
  
# # 使用matplotlib绘制n和耗时之间的函数图像  
# plt.figure(figsize=(10, 6))  # 设置图像大小  
# plt.plot(range(1, 10001), time_n, label='Time taken for sum of arithmetic series')  
# plt.xlabel('n')  # 设置x轴标签  
# plt.ylabel('Time (seconds)')  # 设置y轴标签  
# plt.title('Time taken to compute sum of arithmetic series using iteration')  # 设置图像标题  
# plt.legend()  # 显示图例  
# plt.grid(True)  # 显示网格  
# plt.show()  # 显示图像

# def nested_loops(n, max_depth):  
#     depth = 0  
#     indices = [0] * max_depth  # 存储每个深度的索引  
      
#     while depth < max_depth:  
#         # 在当前深度上迭代  
#         for indices[depth] in range(n):  
#             # 执行一些操作（这里只是打印索引值）  
#             print(indices)  
          
#         # 检查是否达到了最大深度或是否需要回溯到上一层  
#         if indices[depth] == n - 1 and depth < max_depth - 1:  
#             # 如果当前深度的索引达到了n-1，并且还有更深的层次要迭代，则增加深度  
#             depth += 1  
#             indices[depth] = 0  # 重置下一深度的索引为0  
#         elif indices[depth] < n - 1:  
#             # 如果当前深度的索引还没有达到n-1，则继续在当前深度上迭代  
#             continue  
#         else:  
#             # 如果当前是最后一层且索引达到了n-1，则退出循环（但在这个例子中，由于while的条件，这不会发生）  
#             # 实际上，由于我们的逻辑，我们会在达到最后一层且索引为n-1时通过增加depth并重置下一层索引来继续  
#             break  # 这行代码在这个特定逻辑下是多余的，但为了完整性保留  
      
#     # 注意：上面的逻辑实际上不需要break语句，因为while循环的条件会处理所有情况  
  
# # 调用函数  
# nested_loops(3, 3)

# class HanoiTower:  
#     def __init__(self, num_disks):  
#         self.num_disks = num_disks  
#         self.pegs = {'A': [], 'B': [], 'C': []}  
#         self._initialize_pegs()  
  
#     def _initialize_pegs(self):  
#         # Initialize the pegs with disks in descending order on peg A  
#         for i in range(self.num_disks, 0, -1):  
#             self.pegs['A'].append(i)  
  
#     def display_state(self):  
#         # Display the current state of the pegs  
#         print("Current state of the Hanoi Tower:")  
#         for peg, disks in self.pegs.items():  
#             print(f"Peg {peg}: {' '.join(map(str, disks)) if disks else 'empty'}")  
#         print()  
  
#     def move_disk(self, from_peg, to_peg):  
#         # Move a single disk from `from_peg` to `to_peg` if it's legal  
#         if from_peg not in self.pegs or to_peg not in self.pegs:  
#             raise ValueError("Invalid peg specified. Use 'A', 'B', or 'C'.")  
#         if not self.pegs[from_peg]:  # If from_peg is empty  
#             print("Cannot move from an empty peg.")  
#             return  
#         if self.pegs[to_peg] and self.pegs[to_peg][-1] < self.pegs[from_peg][-1]:  # If moving to a smaller disk  
#             print("Cannot move to a peg with a smaller disk on top.")  
#             return  
  
#         disk = self.pegs[from_peg].pop()  
#         self.pegs[to_peg].append(disk)  
#         self.display_state()  
#         print(f"Moved disk {disk} from {from_peg} to {to_peg}")  
  
#     def is_solved(self):  
#         # Check if the tower is solved (all disks on peg C in descending order)  
#         return self.pegs['C'] == list(range(self.num_disks, 0, -1)) and not self.pegs['A'] and not self.pegs['B']  
  
#     def play_game(self):  
#         # Main game loop  
#         while not self.is_solved():  
#             valid_moves = []  
#             for from_peg in self.pegs:  
#                 if self.pegs[from_peg]:  # If the peg is not empty  
#                     for to_peg in self.pegs:  
#                         if from_peg != to_peg:  # Cannot move to the same peg  
#                             if not self.pegs[to_peg] or self.pegs[to_peg][-1] > self.pegs[from_peg][-1]:  # Legal move  
#                                 valid_moves.append((from_peg, to_peg))  
  
#             if not valid_moves:  
#                 print("No valid moves left.")  
#                 break  
  
#             # Prompt user for move  
#             print("Valid moves:")  
#             for i, (from_peg, to_peg) in enumerate(valid_moves, 1):  
#                 print(f"{i}. From {from_peg} to {to_peg}")  
#             choice = input("Choose a move (enter the number): ")  
  
#             try:  
#                 choice = int(choice) - 1  # Convert to zero-based index  
#                 from_peg, to_peg = valid_moves[choice]  
#                 self.move_disk(from_peg, to_peg)  
#             except (IndexError, ValueError):  
#                 print("Invalid choice. Please try again.")  
  
#             # Optionally, automatically find and execute the next move (solving the puzzle)  
#             # Uncomment the following line to enable auto-solving after each user move  
#             # if not self.is_solved():  
#             #     next_move = self.find_next_move()  
#             #     self.move_disk(next_move[0], next_move[1])  
  
#         if self.is_solved():  
#             print("Congratulations! You solved the Hanoi Tower!")  
  
#     # Optional: A helper method to find the next legal move (for auto-solving or debugging)  
#     # def find_next_move(self):  
#     #     for from_peg in self.pegs:  
#     #         for to_peg in self.pegs:  
#     #             if from_peg != to_peg and (not self.pegs[to_peg] or self.pegs[to_peg][-1] > self.pegs[from_peg][-1]):  
#     #                 return (from_peg, to_peg)  
#     #     return None  
  
# # Example usage:  
# if __name__ == "__main__":  
#     num_disks = int(input("Enter the number of disks for the Hanoi Tower: "))  
#     hanoi = HanoiTower(num_disks)  
#     hanoi.display_state()  
#     hanoi.play_game()


# coding :utf-8
# Create by wwx on 2018-12-6

'''
pygame创建显示层

小写的变量代表坐标，大写的变量代表数值

整条蛇就是一个一维的数组，整个图也是一个一维数组。
* 处既为坐标（1,1）对应一维数组蛇的 1 * WIDTH + 1
@ 处为食物的初始位置 4 * WIDTH + 7
#  #  #  #  #  #  #  #  #  #  #  #  #  #  #
#  *                                      #
#                                         #
#                                         #
#                                         #
#                                         #
#                                         #
#           @                             #
#                                         #
#                                         #
#                                         #
#                                         #
#                                         #
#                                         #
#  #  #  #  #  #  #  #  #  #  #  #  #  #  #

检查cell（小方格）有没有让蛇覆盖
检查某个位置idx是否可以向某个方向运动
每次吃掉食物后需要重新刷新地图，重置food
BFS 遍历整个board 计算蛇与食物的路径长度
需要选择最短路径
检查蛇头与蛇尾的位置，避免发生没有路径可走

让蛇头朝着蛇尾运行一步，不管蛇身阻挡，朝蛇尾方向运行

随机生成食物
真正的蛇运动
虚假的蛇运动
'''

"""
import pygame
import sys
import time
import random
from pygame.locals import *

#定义一些颜色变量，背景色
blackColour = pygame.Color(0,0,0)
redColour = pygame.Color(255,0,0)
greenColour = pygame.Color(0,255,0)
whiteColour = pygame.Color(255,255,255)
headColour = pygame.Color(0,119,255)

#定义蛇的场地长宽，HEIGHT为行，WIDTH为列，，，围栏需要各占一列或者一行，实际上为13*13
HEIGHT = 15#高度
WIDTH = 15#宽度  WIDTH为围栏
FIELD_SIZE = HEIGHT * WIDTH #字段大小等于长乘以宽
HEAD = 0 #定义蛇头的位置 位于snake数组的第一个位置

#用数字代表不同的对象，运动时矩阵上每个格子会处理成到达食物的路径长度
# 因此这三个变量间需要有足够大的间隔(>HEIGHT*WIDTH)来互相区分
UNDEFINED = (HEIGHT + 1) * (WIDTH + 1)#当字段大小大于等于UNDEFINED的时候就终止蛇的运动
SNAKE = 2 * UNDEFINED
FOOD = 0#食物


# 由于snake是一维数组，所以对应元素直接加上以下值就表示向四个方向移动
LEFT = -1
RIGHT = 1
UP = -WIDTH#一维数组，所以需要整个宽度都加上才能表示上下移动
DOWN = WIDTH

# 错误码
ERR = -1111

# 用一维数组来表示二维的东西
#board表示蛇运动的矩形场地
board = [0] * FIELD_SIZE #[0,0,0,......]   一维数组的初始化
snake = [0] * (FIELD_SIZE + 1)
snake[HEAD] = 1 * WIDTH + 1 # 初始化蛇头在(1,1)的地方
snake_size = 1#定义蛇的长度为1

# 与上面变量对应的临时变量，蛇试探性地移动时使用，既在蛇真正的开始运动之前，先模拟一次
tmpboard = [0] * FIELD_SIZE
tmpsnake = [0] * (FIELD_SIZE + 1)
tmpsnake[HEAD] = 1 * WIDTH + 1
tmpsnake_size = 1

food = 4 * WIDTH + 7  # food:食物位置初始在(4, 7)
best_move = ERR  # best_move: 运动方向，最终确定的方向

# 运动方向数组，游戏分数(蛇长)
mov = [LEFT, RIGHT, UP, DOWN]#蛇能够运动的四个方向

score = 1#分数，蛇触碰到食物，score就加一



# 检查一个cell有没有被蛇身覆盖，没有覆盖则为free，返回true
def is_cell_free(idx, psize, psnake):
    return not (idx in psnake[:psize])

# 检查某个位置idx是否可向move方向运动
def is_move_possible(idx, move):
    flag = False
    if move == LEFT:
        # 因为实际范围是13*13,[1,13]*[1,13],所以idx为1时不能往左跑，此时取余为1所以>1
        flag = True if idx % WIDTH > 1 else False
    elif move == RIGHT:
        # 这里的<WIDTH-2跟上面是一样的道理
        flag = True if idx % WIDTH < (WIDTH - 2) else False
    elif move == UP:
        # 这里向上的判断画图很好理解，因为在[1,13]*[1,13]的实际运动范围外，还有个
        # 大框是围墙，就是之前说的那几个行列，下面判断向下运动的条件也是类似的
        flag = True if idx > (2 * WIDTH - 1) else False
    elif move == DOWN:
        flag = True if idx < (FIELD_SIZE - 2 * WIDTH) else False
    return flag

# 重置board
# board_BFS后，UNDEFINED值都变为了到达食物的路径长度
# 如需要还原，则要重置它
def board_reset(psnake, psize, pboard):#刷新食物
    for i in range(FIELD_SIZE):
        if i == food:
            pboard[i] = FOOD
        elif is_cell_free(i, psize, psnake):  # 该位置为空
            pboard[i] = UNDEFINED
        else:  # 该位置为蛇身
            pboard[i] = SNAKE

# 广度优先搜索遍历整个board，
# 计算出board中每个非SNAKE元素到达食物的路径长度
def board_BFS(pfood, psnake, pboard):
    queue = []
    queue.append(pfood)
    inqueue = [0] * FIELD_SIZE
    found = False
    # while循环结束后，除了蛇的身体，
    # 其它每个方格中的数字为从它到食物的曼哈顿间距
    while len(queue) != 0:
        idx = queue.pop(0)  # 初始时idx是食物的坐标
        if inqueue[idx] == 1: continue
        inqueue[idx] = 1
        for i in range(4):  # 左右上下
            if is_move_possible(idx, mov[i]):
                if idx + mov[i] == psnake[HEAD]:
                    found = True
                if pboard[idx + mov[i]] < SNAKE:  # 如果该点不是蛇的身体
                    if pboard[idx + mov[i]] > pboard[idx] + 1:  # 小于的时候不管，不然会覆盖已有的路径数据
                        pboard[idx + mov[i]] = pboard[idx] + 1
                    if inqueue[idx + mov[i]] == 0:
                        queue.append(idx + mov[i])
    return found

# 从蛇头开始，根据board中元素值，
# 从蛇头周围4个领域点中选择最短路径
def choose_shortest_safe_move(psnake, pboard):
    best_move = ERR
    min = SNAKE
    for i in range(4):
        if is_move_possible(psnake[HEAD], mov[i]) and pboard[psnake[HEAD] + mov[i]] < min:
            # 这里判断最小和下面的函数判断最大，都是先赋值，再循环互相比较
            min = pboard[psnake[HEAD] + mov[i]]
            best_move = mov[i]
    return best_move

# 从蛇头开始，根据board中元素值，
# 从蛇头周围4个领域点中选择最远路径
def choose_longest_safe_move(psnake, pboard):
    best_move = ERR
    max = -1
    for i in range(4):
        if is_move_possible(psnake[HEAD], mov[i]) and pboard[psnake[HEAD] + mov[i]] < UNDEFINED and pboard[
            psnake[HEAD] + mov[i]] > max:
            max = pboard[psnake[HEAD] + mov[i]]
            best_move = mov[i]
    return best_move

# 检查是否可以追着蛇尾运动，即蛇头和蛇尾间是有路径的
# 为的是避免蛇头陷入死路
# 虚拟操作，在tmpboard,tmpsnake中进行
def is_tail_inside():
    global tmpboard, tmpsnake, food, tmpsnake_size
    tmpboard[tmpsnake[tmpsnake_size - 1]] = 0  # 虚拟地将蛇尾变为食物(因为是虚拟的，所以在tmpsnake,tmpboard中进行)
    tmpboard[food] = SNAKE  # 放置食物的地方，看成蛇身
    result = board_BFS(tmpsnake[tmpsnake_size - 1], tmpsnake, tmpboard)  # 求得每个位置到蛇尾的路径长度
    for i in range(4):  # 如果蛇头和蛇尾紧挨着，则返回False。即不能follow_tail，追着蛇尾运动了
        if is_move_possible(tmpsnake[HEAD], mov[i]) and tmpsnake[HEAD] + mov[i] == tmpsnake[
            tmpsnake_size - 1] and tmpsnake_size > 3:
            result = False
    return result

# 让蛇头朝着蛇尾运行一步
# 不管蛇身阻挡，朝蛇尾方向运行
def follow_tail():
    global tmpboard, tmpsnake, food, tmpsnake_size
    tmpsnake_size = snake_size
    tmpsnake = snake[:]
    board_reset(tmpsnake, tmpsnake_size, tmpboard)  # 重置虚拟board
    tmpboard[tmpsnake[tmpsnake_size - 1]] = FOOD  # 让蛇尾成为食物
    tmpboard[food] = SNAKE  # 让食物的地方变成蛇身
    board_BFS(tmpsnake[tmpsnake_size - 1], tmpsnake, tmpboard)  # 求得各个位置到达蛇尾的路径长度
    tmpboard[tmpsnake[tmpsnake_size - 1]] = SNAKE  # 还原蛇尾
    return choose_longest_safe_move(tmpsnake, tmpboard)  # 返回运行方向(让蛇头运动1步)

# 在各种方案都不行时，随便找一个可行的方向来走(1步),
def any_possible_move():
    global food, snake, snake_size, board
    best_move = ERR
    board_reset(snake, snake_size, board)
    board_BFS(food, snake, board)
    min = SNAKE

    for i in range(4):
        if is_move_possible(snake[HEAD], mov[i]) and board[snake[HEAD] + mov[i]] < min:
            min = board[snake[HEAD] + mov[i]]
            best_move = mov[i]
    return best_move

# 转换数组函数
def shift_array(arr, size):
    for i in range(size, 0, -1):
        arr[i] = arr[i - 1]

#随机生成新的食物
def new_food():
    global food,snake_size
    cell_free = False
    while not cell_free:
        w = random.randint(1,WIDTH - 2)#随机
        h = random.randint(1, HEIGHT - 2)#随机
        food = WIDTH * h + w#随机坐标
        cell_free = is_cell_free(food, snake_size, snake)#判断新产生的food是否合法
        pygame.draw.rect(playSurface, redColour, Rect(18 * (food / WIDTH), 18 * (food % WIDTH), 18, 18))


# 真正的蛇在这个函数中，朝pbest_move走1步
def make_move(pbest_move):
    global key, snake, board, snake_size, score
    shift_array(snake, snake_size)
    snake[HEAD] += pbest_move
    p = snake[HEAD]
    for body in snake:  # 画蛇，身体，头，尾
        pygame.draw.rect(playSurface, whiteColour, Rect(18 * (body / WIDTH), 18 * (body % WIDTH), 18, 18))
    pygame.draw.rect(playSurface, greenColour,
                     Rect(18 * (snake[snake_size - 1] / WIDTH), 18 * (snake[snake_size - 1] % WIDTH), 18, 18))
    pygame.draw.rect(playSurface, headColour, Rect(18 * (p / WIDTH), 18 * (p % WIDTH), 18, 18))
    # 这一行是把初始情况会出现的第一个白块bug填掉
    pygame.draw.rect(playSurface, blackColour, Rect(0, 0, 18, 18))
    # 刷新pygame显示层
    pygame.display.flip()

    # 如果新加入的蛇头就是食物的位置
    # 蛇长加1，产生新的食物，重置board(因为原来那些路径长度已经用不上了)
    if snake[HEAD] == food:
        board[snake[HEAD]] = SNAKE  # 新的蛇头
        snake_size += 1
        score += 1
        if snake_size < FIELD_SIZE: new_food()
    else:  # 如果新加入的蛇头不是食物的位置
        board[snake[HEAD]] = SNAKE  # 新的蛇头
        board[snake[snake_size]] = UNDEFINED  # 蛇尾变为UNDEFINED，黑色
        pygame.draw.rect(playSurface, blackColour,
                         Rect(18 * (snake[snake_size] / WIDTH), 18 * (snake[snake_size] % WIDTH), 18, 18))
        # 刷新pygame显示层
        pygame.display.flip()

    # 虚拟地运行一次，然后在调用处检查这次运行可否可行


# 可行才真实运行。
# 虚拟运行吃到食物后，得到虚拟下蛇在board的位置
def virtual_shortest_move():
    global snake, board, snake_size, tmpsnake, tmpboard, tmpsnake_size, food
    tmpsnake_size = snake_size
    tmpsnake = snake[:]  # 如果直接tmpsnake=snake，则两者指向同一处内存
    tmpboard = board[:]  # board中已经是各位置到达食物的路径长度了，不用再计算
    board_reset(tmpsnake, tmpsnake_size, tmpboard)

    food_eated = False
    while not food_eated:
        board_BFS(food, tmpsnake, tmpboard)
        move = choose_shortest_safe_move(tmpsnake, tmpboard)
        shift_array(tmpsnake, tmpsnake_size)
        tmpsnake[HEAD] += move  # 在蛇头前加入一个新的位置
        # 如果新加入的蛇头的位置正好是食物的位置
        # 则长度加1，重置board，食物那个位置变为蛇的一部分(SNAKE)
        if tmpsnake[HEAD] == food:
            tmpsnake_size += 1
            board_reset(tmpsnake, tmpsnake_size, tmpboard)  # 虚拟运行后，蛇在board的位置
            tmpboard[food] = SNAKE
            food_eated = True
        else:  # 如果蛇头不是食物的位置，则新加入的位置为蛇头，最后一个变为空格
            tmpboard[tmpsnake[HEAD]] = SNAKE
            tmpboard[tmpsnake[tmpsnake_size]] = UNDEFINED


# 如果蛇与食物间有路径，则调用本函数
def find_safe_way():
    global snake, board
    safe_move = ERR
    # 虚拟地运行一次，因为已经确保蛇与食物间有路径，所以执行有效
    # 运行后得到虚拟下蛇在board中的位置，即tmpboard
    virtual_shortest_move()  # 该函数唯一调用处
    if is_tail_inside():  # 如果虚拟运行后，蛇头蛇尾间有通路，则选最短路运行(1步)
        return choose_shortest_safe_move(snake, board)
    safe_move = follow_tail()  # 否则虚拟地follow_tail 1步，如果可以做到，返回true
    return safe_move


#初始化pygame
pygame.init()
#定义一个变量来控制游戏速度
fpsClock = pygame.time.Clock()

#创建pygame显示层
playSurface = pygame.display.set_mode((300,300))#创建一个300*300的窗口
pygame.display.set_caption('贪吃蛇')#游戏的title
playSurface.fill(blackColour)# 绘制pygame显示层
#初始化food
pygame.draw.rect(playSurface, redColour, Rect(18 * (food / WIDTH), 18 * (food % WIDTH), 18, 18))
while True:
    #刷新pygame显示层
    pygame.display.flip()#保持窗口一直存在
    # 重置距离
    board_reset(snake, snake_size, board)
    # 如果蛇可以吃到食物，board_BFS返回true
    # 并且board中除了蛇身(=SNAKE)，其它的元素值表示从该点运动到食物的最短路径长
    if board_BFS(food, snake, board):
        best_move = find_safe_way()  # find_safe_way的唯一调用处
    else:
        best_move = follow_tail()
    if best_move == ERR:
        best_move = any_possible_move()
    # 上面一次思考，只得出一个方向，运行一步
    if best_move != ERR:
        make_move(best_move)
    else:
        break
    # 控制游戏速度
    fpsClock.tick(120)  # 20看上去速度正好
print(score)  # 游戏结束后打印分数
"""


"""
import turtle  
import numpy as np   
  
def draw_function(func, lower_bound, upper_bound, n = 400):  
    # 设置画布  
    screen = turtle.Screen()  
    screen.setworldcoordinates(lower_bound, -10, upper_bound, 10)  
    graph = turtle.Turtle()  
    graph.speed(0)  # 设置绘画速度，0 表示最快  
      
    # 绘制x轴和y轴  
    graph.penup()  
    graph.goto(lower_bound, 0)  
    graph.pendown()  
    graph.goto(upper_bound, 0)  
      
    graph.penup()  
    graph.goto(0, -10)  
    graph.pendown()  
    graph.goto(0, 10)  
      
    # 使用NumPy生成x值的数组，并计算y值  
    x_values = np.linspace(lower_bound, upper_bound, n)  # 生成n个点  
    y_values = np.vectorize(func)(x_values)  # 计算y值  
      
    # 过滤掉NaN和无穷大的值  
    valid_points = ~np.isnan(y_values) & ~np.isinf(y_values)  
    x_values = x_values[valid_points]  
    y_values = y_values[valid_points]  
      
    # 绘制函数  
    graph.penup()  
    for x, y in zip(x_values, y_values):  
        graph.goto(x, y)  
        graph.pendown()  
      
    graph.penup()  
      
    # 隐藏海龟并显示图像  
    graph.hideturtle()  
    turtle.done()  
  
# 示例函数  
def example_function(x):  
    return np.sin(1/x)  
  
# 调用绘制函数  
draw_function(example_function, -np.pi / 100, np.pi / 100, 10000)
"""

"""
def find_max_arry_n(lst, n):  
    if n == 1:  
        return max(lst)  
    elif n == len(lst):  
        return sum(lst)  
      
    temp = sum(lst[:n])  
    max_sum = temp  
  
    for i in range(len(lst) - n):  
        temp = temp - lst[i] + lst[i + n]  
        if temp > max_sum:  
            max_sum = temp  
  
    return max_sum  
  
def fin_max_arry(lst):  
    if not lst:  
        return 0  # 如果列表为空，返回0或适当的值  
    max_sum = find_max_arry_n(lst, 1)  
    for i in range(2, len(lst) + 1):  
        temp = find_max_arry_n(lst, i)  
        if max_sum < temp:  
            max_sum = temp  
  
    return max_sum  
  
l1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]  
l2 = [1]  
l3 = [5, 4, -1, 7, 8]  
print(fin_max_arry(l1))   
print(fin_max_arry(l2))    
print(fin_max_arry(l3))
"""

import numpy as np
import pygame

# 初始化pygame
pygame.init()

# 设置窗口大小和标题
screen_size = (800, 800)
screen = pygame.display.set_mode(screen_size)
pygame.display.set_caption('Ball Movement in Circle')

# 加载字体（选择一个支持中文的字体）
try:
    font = pygame.font.SysFont('SimHei', 16)  # 尝试使用SimHei字体，字号为16
except:
    font = pygame.font.SysFont('msyh', 16)  # 如果SimHei不可用，回退到msyh

# 初始化参数
gravity = np.array([0, -9.8])  # 重力加速度
dt = 0.01  # 时间步长
fps = 120  # 动画帧率（合理设置以避免过高的CPU使用率）
clock = pygame.time.Clock()  # 控制帧率

# 定义小球类
class Ball:
    def __init__(self, position, velocity, radius, color):
        self.position = np.array(position)
        self.velocity = np.array(velocity)
        self.radius = radius
        self.color = color
        self.trail = []
        self.max_trail_length = 2000

    def update_position(self, grav, dt):
        new_vel = self.velocity + grav * dt
        new_pos = self.position + new_vel * dt
        self.position, self.velocity = new_pos, new_vel

    def check_boundary(self, center, radius):
        if not np.linalg.norm(self.position - center) <= radius:
            direction = self.position - center
            direction /= np.linalg.norm(direction)
            self.position = center + direction * radius * (1 - 1e-6)
            self.velocity = -self.velocity * 1.1

    def add_to_trail(self):
        self.trail.append(self.position.copy())
        if len(self.trail) > self.max_trail_length:
            self.trail.pop(0)

    def draw(self, screen):
        # 画小球
        pygame.draw.circle(screen, self.color, tuple(map(int, self.position)), self.radius)
        # 画轨迹
        for pos in self.trail:
            pygame.draw.circle(screen, (0, 0, 255), tuple(map(int, pos)), 2)

    def get_energy(self):
        # 计算动能、势能和机械能
        kinetic_energy = 0.5 * np.sum(self.velocity ** 2)
        potential_energy = np.dot(self.position, gravity)
        mechanical_energy = kinetic_energy + potential_energy
        return kinetic_energy, potential_energy, mechanical_energy

    def get_velocity_components(self):
        return self.velocity[0], self.velocity[1]

# 创建小球对象列表
balls = [
    Ball(position=[400, 300], velocity=[10, 5], radius=10, color=(255, 0, 0)),
    # 可以添加更多小球对象
]

# 圆的边界参数
center = np.array([400, 400])
boundary_radius = 300

# 主循环
running = True
while running:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False

    # 更新小球状态
    for ball in balls:
        ball.update_position(gravity, dt)
        ball.check_boundary(center, boundary_radius)
        ball.add_to_trail()

    # 清屏
    screen.fill((255, 255, 255))

    # 画圆边界
    pygame.draw.circle(screen, (0, 0, 0), tuple(center), boundary_radius, 2)

    # 画小球和轨迹
    for ball in balls:
        ball.draw(screen)

    # 显示小球信息
    y_offset = 10
    for idx, ball in enumerate(balls):
        ke, pe, me = ball.get_energy()
        vx, vy = ball.get_velocity_components()

        # 为每个小球构建信息文本
        info_text = [
            f"球{idx + 1}：",
            f"动能：  {ke:.2e}",
            f"势能：  {pe:.2e}",
            f"机械能：{me:.2e}",
            f"速度： ({vx:.2f}, {vy:.2f})",
            f"加速度:({gravity[0]:.2f}, {gravity[1]:.2f})"
        ]

        # 将信息文本逐行渲染到屏幕上
        for line in info_text:
            text_surface = font.render(line, True, (0, 0, 0))
            screen.blit(text_surface, (10, y_offset))
            y_offset += 20

    # 更新显示
    pygame.display.flip()

    # 控制帧率
    clock.tick(fps)

# 退出pygame
pygame.quit()